package com.kevinkk.dp;

/**
 * 你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
 * 给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
 *
 * 分为两种情况讨论，要么考虑包含首元素，不包含尾元素
 *                要么考虑包含尾元素，不包含首元素
 */

public class HouseRobberII {
    class Solution {
        public int rob(int[] nums) {
            int length = nums.length;
            if(length == 1) return nums[0];
            int[] preNum = new int[length-1], postNum = new int[length-1];
            System.arraycopy(nums, 0, preNum, 0, length-1);
            System.arraycopy(nums, 1, postNum, 0, length-1);
            return Math.max(myRob(preNum), myRob(postNum));
        }

        private int myRob(int[] nums) {
            int[] dp = new int[nums.length];
            if (nums.length == 1)
                return nums[0];
            dp[0] = nums[0];
            dp[1] = Math.max(nums[0], nums[1]);
            for (int i = 2; i < nums.length; i++)
                dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);

            return dp[nums.length - 1];
        }
    }
}
